/*
 * @lc app=leetcode.cn id=94 lang=cpp
 *
 * [94] 二叉树的中序遍历
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution
{
 public:
  // 递归写法
  /*
   vector<int> res;
   vector<int> inorderTraversal(TreeNode* root)
   {
     bfs(root);
     return results;
   }
   void bfs(TreeNode* node)
   {
     if (node == NULL) return;
     bfs(node->left);
     res.push_back(node->val);
     bfs(node->right);
   }*/

  vector<int> inorderTraversal(TreeNode* root)
  {
    vector<int> res;
    // 改为迭代一定是用一个stack或者数组来存储，代替系统栈
    stack<TreeNode*> stk;

    TreeNode* p = root;
    while (p || stk.size())
    {
      // 左子树入栈
      while (p)
      {
        stk.push(p);
        p = p->left;
      }

      // 开始打印左
      p = stk.top();
      stk.pop();
      res.push_back(p->val);

      // 某节点有右子树，右子树入栈
      p = p->right;
    }
    return res;
  }
};
// @lc code=end
